#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#define rep(i,a,b) for(int i = (a);i <= b;++i)
#define per(i,a,b) for(int i = (a);i >= b;--i)
#define mkp std::make_pair
#define pr std::pair
typedef long long ll;
typedef unsigned long long ull;
using std::cin;using std::cout;using std::cerr;using std::string;
const int N = 1e6+9;
const int inf = 1e9+9;
const double eps = 1e-7;
int n,m,c,k;
ull a[2*N],p[2*N],tmp[2*N],ref[2*N],sum,q[2*N],tot;
bool flag[2*N],cant[2*N];

inline bool cmp(int x,int y){return x<y;}

inline ull _pow(ull x,ull p){
    ull ans = 1 , base = x; 
    while(p){
	    if(p&1) ans *= base;
	    base *= base;
	    p >>= 1ull;
    }
    return ans;
}

int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> n >> m >> c >> k;
    rep(i,1,n) cin >> a[i];
    rep(i,1,n) tot = tot | a[i];
    rep(i,1,m) cin >> p[i] >> q[i];
    for(ll i = 0;i <= k-1;++i){
	    if((1ull << i) & tot) flag[i] = true;
    }
    rep(i,1,m){
	    if(flag[ p[i] ] || cant[ p[i] ]) continue;
	    cant[ p[i] ] = true;
	    ++sum;
    }
    if(!n && k == 64) cout << "18446744073709551616\n";
    else cout << _pow(2,k-sum) - n << "\n";   
    return 0;
}
    